package 树与图.字典树;

import java.util.Stack;

/**
 * 230. 二叉搜索树中第 K 小的元素
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
 *
 * 思路：采用中序遍历维护升序队列，当遍历到第k个数时，即返回该值的节点
 *
 */
public class L_230 {

    private int res = 0;
    private int count = 0;

    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inOrder(root);
        return res;
    }

    public boolean inOrder(TreeNode node){
        if(node == null){
            return false;
        }
        // 中序遍历，先遍历左子树
        if(inOrder(node.left)){
            return true;
        }
        // 遍历当前节点,并进行统计
        count --;
        if (count == 0){
            res = node.val;
            return true;
        }

        // 遍历右子树
        return inOrder(node.right);
    }


    /**
     * 使用栈的迭代思路
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest111(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        int count = 0;

        while (curr != null || !stack.isEmpty()) {
            // 遍历到最左节点
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            // 处理当前节点
            curr = stack.pop();
            count++;
            if (count == k) {
                return curr.val; // 找到第k小，直接返回
            }

            // 转向右子树
            curr = curr.right;
        }

        return -1; // 题目保证k有效，此处不会执行
    }



    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
